package 链表;

import com.sun.org.apache.xerces.internal.util.SAXLocatorWrapper;

// 1.先用快慢指针找到中间节点
//2.分开链表为左半部分与右半部分
// 3.右边部分利用头插法进行倒序
// 4.两个链表进行分别插入
public class 重排链表Demo {
    static  class ListNode{
        int val;
        ListNode next;
        ListNode prev;
        ListNode(int val){
            this.val = val;
        }
        ListNode(int val, ListNode next){
            this.val = val;
            this.next = next;

        }
    }

    public void reorderList(ListNode head)
    {
        // 处理边界情况
        if(head == null || head.next == null || head.next.next == null)
            return;

        // 1.找距表的中间节点，快慢双指针
        ListNode slow = head,fast = head;
        while(fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        // 2.把slow 后面的部分给逆序，头插
        ListNode head2 = new ListNode(0);
        ListNode cur = slow.next;
        slow.next = null; // 分离链表
        while(cur!=null){
            ListNode next = cur.next;
            cur.next = head2.next;
            head2.next = cur;
            cur = next;
        }
        //3.合并两个链表-双指针
        ListNode cur1 = head,cur2 = head2.next;
        ListNode  ret = new ListNode(0);
        ListNode pre  = ret;
        while(cur1 != null){
            // 先放第一个链表
            pre.next = cur1;
            pre = cur1;
            cur1 = cur1.next;

            // 再合并第二个链表
            if(cur2 !=null){
                pre.next = cur2;
                pre = cur2;
                cur2 = cur2.next;
            }
        }

    }


}
